
package 剑指offer;

import java.util.ArrayList;
import java.util.Stack;

public class 字形打印二叉树 {
    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        Stack<TreeNode> lQueue = new Stack<>();

        Stack<TreeNode> rQueue = new Stack<>();

        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();

        boolean flag = true;
        int count = 0;
        if (pRoot != null) {
            lQueue.push(pRoot);

            while (!lQueue.isEmpty() || !rQueue.isEmpty()) {

                if (flag) {
                    ArrayList<Integer> tempList = new ArrayList<>();
                    while (!lQueue.isEmpty()) {
                        TreeNode peek = lQueue.pop();
                        System.out.print(peek.val + " ");
                        tempList.add(peek.val);
                        if (peek.left != null) {
                            rQueue.push(peek.left);

                        }
                        if (peek.right != null) {
                            rQueue.push(peek.right);

                        }

                    }

                    if (!tempList.isEmpty()) {
                        System.out.println();
                        lists.add(tempList);
                    }
                    flag = false;
                }
                if (!flag) {

                    ArrayList<Integer> tempList = new ArrayList<>();
                    while (!rQueue.isEmpty()) {
                        TreeNode peek = rQueue.pop();
                        System.out.print(peek.val + " ");
                        tempList.add(peek.val);
                        if (peek.right != null) {
                            lQueue.add(peek.right);

                        }
                        if (peek.left != null) {
                            lQueue.add(peek.left);

                        }

                    }

                    if (!tempList.isEmpty()) {
                        System.out.println();
                        lists.add(tempList);
                    }
                    flag = true;
                }
            }
        }
        return lists;

    }

    /*
     * 	      	8
     * 	  6	      10
     *   5 	    7      9      11
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(11);
        Print(root);
    }

}

